#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "set"

using namespace std;

//相对离谱一直没过去用unorder的set过去了
struct Trie {
    Trie *child[26];//树有26个树叉
    //string word = "";
    Trie() {
        for (int i = 0; i < 26; i++)
            child[i] = nullptr;
    }
};

//把树跟传过来
void insertTrie(std::string key, Trie *root) {
    auto cur = root;
    for (int i = 0; i < key.size(); i++) {
        if (cur->child[key[i] - 'a'] == nullptr) {
            cur->child[key[i] - 'a'] = new Trie();
        }
        cur = cur->child[key[i] - 'a'];
    }
    // cur->word=key;//叶子节点存了一个
}

bool findTrie(string key, Trie *root) {
    auto cur = root;

    for (int i = 0; i < key.size(); ++i) {
        cur = cur->child[key[i] - 'a'];
        if (!cur)
            return false;
    }

    return true;

}


class Solution {
public:
    int rowMax = 0;
    int colMax = 0;
    vector<string> ret;
    unordered_set <string> mp;
    vector<char> temp;
    int maxLen = 0;
    Trie root;

    void exist_r(vector<vector<char>> &board, int row, int col) {
        //
        if (row > rowMax || col > colMax || row < 0 || col < 0 || temp.size() >= maxLen)
            return;

        char c = board[row][col];
        if (c == '*')
            return;


        temp.push_back(board[row][col]);
        string tp(temp.begin(), temp.end());


        if ((mp.find(tp) != mp.end())) {
            mp.erase(tp);
            ret.push_back(tp);
        }
        if (!findTrie(tp, &root)) {
            temp.pop_back();
            return;
        }


        board[row][col] = '*';//妈蛋这个得放在这边 temp+board[row][col],
        exist_r(board, row + 1, col);
        exist_r(board, row - 1, col);
        exist_r(board, row, col + 1);
        exist_r(board, row, col - 1);
        temp.pop_back();
        board[row][col] = c;

    }


    vector<string> findWords(vector<vector<char>> &board, vector<string> words) {

        for (auto &item :words) {
            insertTrie(item, &root);
            int a = item.size();
            maxLen = std::max(maxLen, (a));
        }


        rowMax = board.size() - 1;
        colMax = board[0].size() - 1;
        mp.insert(words.begin(), words.end());
        for (int i = 0; i <= rowMax; i++) {
            for (int j = 0; j <= colMax; j++) {
                exist_r(board, i, j);
            }
        }

        return ret;
    }

};